package com.sfx.算法专题.滑动窗口;

public class A总结题型 {
    public static void main(String[] args) {
        int[] res = new int[]{-1,-1};
    }
    /**
        &同向双指针也叫作 "滑动窗口"
        &使用同向双指针 绝大部分都是 维护一段区间,两个指针移动的时候,就形象于 "窗口"

        滑动窗口特点(什么时候使用滑动窗口) :
        1.滑动窗口 本质上就是 "同向双指针"
        2.当暴力方法的时候 "两个指针" 都不回退---> 具有单调性
        如何使用滑动窗口 ?
           初始化两个指针=0 left为左端点,right为右端点
           while(边界条件) {
               2. 进窗口->right先移动,移动到最佳位置,在移动left
               3. 判断是否符合条件,是否要出窗口
           }
           "更新结果" -> 取决于题目要求
           1): 进窗口要更新结果
           2): 判断的时候/出窗口前 要更新结果
           3): 出窗口后 要更新结果
        滑动窗口总结三步骤 :
                1) : 进窗口
                2) : 出窗口
                3) : 更新结果
        总结: 利用 "单调性" -> 先让right指针移动,移动到最佳位置->取决于题目,在移动left

        滑动窗口的正确性 :
           利用了单调性,规避了许多没有必要的枚举行为
        时间复杂度 : O(2*N) --> O(N) 最差情况下:right移动到结尾,left在移动到结尾

        子串与子数组-->都是连续的

         所有的暴力优化总结 :
             1) : 所有的暴力枚举都是,先移动right,达到某一条件后,left++,right从left+1开始
             2) : 现在我们这样优化 先移动right,达到某一条件后,left++,right不变.等某一条件right,在变
         可以发现 两指针不回退,满足单调性.

         滑动窗口可以与哈希表进行结合使用 ,哈希表用于判断某一字符/数字是否重复
         哈希表也可以使用数组替代.

          滑动窗口都有一个特点:
             1): 在使用暴力解法的时候,一个left每次往后移动一次,right都要从left开始
             2): 所以我们可以优化成right不动,left移动到最佳位置,right才动
             3): 这样才符合滑动窗口的使用要求,两指针单调,不回退.
                1): 某一条件变量不变,right不变
                2): 某一条件变量减小,right右移

          可以发现滑动窗口分为两种类型 :
            1): 窗口固定
                  字母异位词,串联单词中的字符串, 使用cnt有效个数来进行优化
            2): 窗口变化
                  1. 不合法出窗口
                  2. 合法出窗口,更新结果  -> 最小覆盖子串

            有时可以使用cnt变量来进行优化
                 1.使用一个变量维护有效个数的个数
                 2.出窗口和进窗口都要进行判断看是否需要更新cnt
            一般出现在两个字符串,找异位词,子串,子数组...
             步骤 :
             1) : 进窗口前更新cnt
             2) : 进窗口
             3) : while/if 条件
             4) : 出窗口
             5) : 出窗口后更新cnt
             6) : 更新结果有可能在出窗口,有可能在出窗口条件之后

              一般滑动窗口要需要与一个数据结构结合使用,有可能是数组(当做哈希表),有可能是哈希表
              哈希表用于统计
     */
}